package stack;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 逆波兰表达式计算器
 */
public class PolandCalculator {
    public static void main(String[] args) {
        //定义一个表达式
        String expression = "1*(2+3)-4";
        ArrayList<String> list = InfixToPostfixConversionList(expression);
        System.out.println(list);
        //先定义一个逆波兰表达式，并把其中的数据和符号用空格隔开
        // String expression = "3 4 + 5 * 6 -";
        //System.out.println(getListString(expression));
        System.out.println(calculate(list));
    }

    /**
     * 将逆波兰表达式存储到list集合里面，并返回
     *
     * @return
     */
    public static ArrayList<String> getListString(String expression) {
        ArrayList<String> list = new ArrayList<>();
        String[] split = expression.split(" ");
        for (String s : split) {
            list.add(s);
        }
        return list;
    }

    /**
     * 将中缀表达式转为后缀表达式
     *
     * @return
     */
    public static ArrayList<String> InfixToPostfixConversionList(String expression) {
        //写出规则 先用正则表达式将中缀表达式中数字拿出来
        String reg = "[()+\\-*/]";
        String[] split1 = expression.split(reg);  
        split1 = Arrays.stream(split1).filter(s -> !s.equals("")).toArray(String[]::new);
        //在用正则表达式将中缀表达式中符号拿出来
        String symbols = "[0-9]+";
        String[] split2 = expression.split(symbols);
        split2 = Arrays.stream(split2).filter(s -> !s.equals("")).toArray(String[]::new);
        ArrayList<String> arrayList = new ArrayList<>();
        for (int i = 0; i < split2.length; i++) {
            if (split2[i].length() > 1) {
                arrayList.add(String.valueOf(split2[i].charAt(0)));
                arrayList.add(String.valueOf(split2[i].substring(1, 2)));
                continue;
            }
            arrayList.add(split2[i]);
        }
        split2 = arrayList.stream().toArray(String[]::new);
        ArrayList<String> list = new ArrayList<>();
        //符号list到哪一个了
        int index = 0;
        for (int i = 0; i < split1.length; i++) {
            if (index < split2.length) {
                if (split2[index].equals("(")) {
                    list.add(split2[index]);
                    index++;
                }
            }
            if (i == split1.length - 1) {
                list.add(split1[i]);
                break;
            }
            list.add(split1[i]);
            if (split2[index].equals(")")) {
                list.add(split2[index]);
                index++;
            }
            list.add(split2[index]);
            index++;
        }
        //以上成功将中缀表达式存储到list中
        Stack<String> stack1 = new Stack<>();//存数字
        Stack<String> stack2 = new Stack<>();//存符号
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i).matches("\\d+")){
                stack1.push(list.get(i));
                continue;
            }
            if (list.get(i).equals("(")) {
                stack2.push(list.get(i));
                continue;
            }
            if (list.get(i).equals(")")) {
                while (!stack2.peek().equals("(")) {
                    stack1.push(stack2.pop());
                }
                stack2.pop();
                continue;
            }
            if (stack2.isEmpty() || stack2.peek() == "(") {
                stack2.push(list.get(i));
                continue;
            }
            if (list.get(i).equals("*") || list.get(i).equals("/")) {
                stack2.push(list.get(i));
                continue;
            }
            if (list.get(i).equals("+") || list.get(i).equals("-")) {
                if (!stack2.peek().equals("*") & !stack2.peek().equals("/")) {
                    stack2.push(list.get(i));
                } else {
                    stack1.push(stack2.pop());
                    stack2.push(list.get(i));
                }
            }
        }
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        ArrayList<String> result = new ArrayList<String>();
        while (!stack1.isEmpty()) {
            result.add(stack1.pop());
        }
        Collections.reverse(result);
        return result;
    }

    //计算表达式的值
    public static int calculate(ArrayList<String> list) {
        //创建初始化栈 只需要存储数据
        Stack<Integer> stack = new Stack<>();
        for (String s : list) {
            if (s.matches("\\d+")) {
                //是数字
                stack.push(Integer.parseInt(s));
            } else {
                //是符号
                int num1 = stack.pop();
                int num2 = stack.pop();
                int res = 0;
                if (s.equals("*")) {
                    res = num1 * num2;
                } else if (s.equals("/")) {
                    res = num2 / num1;
                } else if (s.equals("+")) {
                    res = num1 + num2;
                } else if (s.equals("-")) {
                    res = num2 - num1;
                } else {
                    throw new RuntimeException("符号错误");
                }
                stack.push(res);
            }
        }
        return stack.pop();
    }
}
